/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-10-12
 * Time: 20:06
 */
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

//还可以用头插法和递归法
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(head.next==null||left==right){
            return head;
        }
        //先找到left
        ListNode prev=null;
        ListNode cur=head;
        ListNode next=head.next;
        int count=1;
        while(count!=left){
            prev=cur;
            cur=next;
            next=next.next;
            count++;
        }
        //找到left


        //记录前驱位置
        ListNode tail=prev;
        //记录断开位置
        ListNode tail2=cur;
        //先从left断开
        if(prev!=null){
            prev.next=null;
        }


        //开始反转
        prev=null;
        count=1;
        while(count<=(right-left+1)){
            cur.next=prev;
            prev=cur;
            cur=next;
            if(next!=null){
                next=next.next;
            }else{
                break;
            }
            count++;
        }

        //反转完开始链接
        if(tail!=null){
            tail.next=prev;
            tail2.next=cur;
            return head;
        }else{
            tail2.next=cur;
            return prev;
        }
    }
}
